翻訳と辞書 Words near each other ・ Geometric networks ・ Geometric phase ・ Geometric phase analysis ・ Geometric Poisson distribution ・ Geometric primitive ・ Geometric probability ・ Geometric programming ・ Geometric progression ・ Geometric quantization ・ Geometric quotient ・ Geometric separator ・ Geometric series ・ Geometric shape ・ Geometric Shapes ・ Geometric Shapes Extended ・ Geometric spanner ・ Geometric stable distribution ・ Geometric standard deviation ・ Geometric Technologies, Inc. ・ Geometric terms of location ・ Geometric tomography ・ Geometric topology ・ Geometric topology (disambiguation) ・ Geometric topology (object) ・ Geometric tortoise ・ Geometric transformation ・ Geometrical acoustics ・ Geometrical frustration ・ Geometrical optics ・ Geometrical-optical illusions Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Geometric spanner ： ウィキペディア英語版 Geometric spanner A geometric spanner or a ''t''-spanner graph or a ''t''-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a ''t''-path between any pair of vertices for a fixed parameter ''t''. A ''t''-path is defined as a path through the graph with weight at most ''t'' times the spatial distance between its endpoints. The parameter ''t'' is called the stretch factor or dilation factor of the spanner.〔.〕 In computational geometry, the concept was first discussed by L.P. Chew in 1986,〔.〕 although the term "spanner" was not used in the original paper. The notion of graph spanners has been known in graph theory: ''t''-spanners are spanning subgraphs of graphs with similar dilation property, where distances between graph vertices are defined in graph-theoretical terms. Therefore geometric spanners are graph spanners of complete graphs embedded in the plane with edge weights equal to the distances between the embedded vertices in the corresponding metric. Spanners may be used in computational geometry for solving some proximity problems. They have also found applications in other areas, such as in motion planning, in telecommunication networks: network reliability, optimization of roaming in mobile networks, etc. ==Different spanners and quality measures== There are different measures which can be used to analyze the quality of a spanner. The most common measures are edge count, total weight and maximum vertex degree. Asymptotically optimal values for these measures are $O(n)$ edges, $O(MST)$ weight and $O(1)$ maximum degree (here MST denotes the weight of the minimum spanning tree). Finding a ''spanner'' in the Euclidean plane with minimal dilation over ''n'' points with at most ''m'' edges is known to be NP-hard.〔.〕 Many spanner algorithms exist which excel in different quality measures. Fast algorithms include the WSPD spanner and the Theta graph which both construct spanners with a linear number of edges in $O(n\; \backslash log\; n)$ time. If better weight and vertex degree is required the Greedy spanner can be computed in near quadratic time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Geometric spanner」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.